//
// Created by 高森森 on 2022/1/28.
//

#ifndef LEETCODE_SOLUTION12_H
#define LEETCODE_SOLUTION12_H
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution12 {
public:
    vector<int>visited;
    bool dfs(int i, vector<vector<int>>&graph){
       if(visited[i]==1)//访问过的顶点
           return false;
       else if(visited[i]==2)//安全的顶点
           return true;
       visited[i]=1;
       for(int neigh:graph[i]){
           if(!dfs(neigh,graph)){
               return false;
           }
       }
       visited[i]=2;
        return true;
    }
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int>result;
        int n=graph.size();
        visited.assign(n,0);
        for(int i=0;i<n;i++){
            if(dfs(i,graph))
                result.push_back(i);
        }
        return result;
    }

    vector<int> eventualSafeNodes1(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<vector<int>>rerverse(n);
        vector<int>rudu(n);
        for(int i=0;i<n;i++)
        {
            for(int neigh:graph[i]){
                rerverse[neigh].push_back(i);
            }
            rudu[i]=graph[i].size();
        }
        queue<int>que;
        for(int i=0;i<n;i++){
            if(rudu[i]==0){
                que.push(i);
            }
        }
        while(!que.empty()){
            int node=que.front();
            que.pop();
            for(int x:graph[node]){
                if(--rudu[x]==0)
                    que.push(x);
            }
        }
        vector<int>result;
        for(int i=0;i<n;i++){
            if(rudu[i]==0){
                result.push_back(i);
            }
        }
        return result;
    }
};


#endif //LEETCODE_SOLUTION12_H
